package independent;

import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: fzykd
 * Date: 2022-11-15
 * Time: 10:58
 */

//快速排序是对冒泡排序的改进
public class QuickSort {
    //原理: 通过一趟排序将排序的数据分割成独立的两个部分
    //其中一个部分的所有数据都要比另外的所有数组都要小 然后 在按此方法对这两部分数据分别进行快速排序
    //排序的过程是递归进行的
    public static void main(String[] args) {
        int[] arr = {23,15,56,9,31,47,3};

        quickSort(arr,0, arr.length-1);

        System.out.println(Arrays.toString(arr));
    }

    private static void quickSort(int[] arr ,int left,int right) {
        //定义一个双指针
        int l = left;
        int r = right;
        //先确定一个基准值
        int pivot = arr[(l+r)/2];

        //交换变量
        int tmp = 0;
        //只要左边的指针 小于 右边的指针 那么循环还可以进行
        while (l < r){
            //在左边的基本一直找 找到一个比基准大的停下来
            while (arr[l] < pivot){
                l+=1;
            }
            //在右边的基准一直找 找到一个比基准小的值停下来
            while (arr[r] > pivot){
                r -= 1;
            }
            //前提条件是 l < r
            //如果 l >= r
            //说明左边已经是都小于pivot 右边都是大于的 那么就结束本次循环
            if (l>=r){
                break;
            }
            //反之 在停下来的l和r进行交换
            tmp = arr[l];
            arr[l] = arr[r];
            arr[r] = tmp;


            //如果交换完之后 arr[l] == pivot 相等 那么++
            if (arr[l] == pivot){
                r -= 1;
            }
            //如果交换完之后 发现这个arr[r] == pivot 那么++后移
            if (arr[r] == pivot){
                l += 1;
            }
        }
        //如果1 == r必须l++ , r-- 否则会出现栈溢出
        if (l == r){
            l +=1;
            r -=1;
        }
        //向左递归
        if (left < r){
            quickSort(arr,left,r);
        }
        //向右递归
        if (right > l){
            quickSort(arr,l,right);
        }

    }
}
